package leetcode.tree;

import java.util.ArrayDeque;

public class Lc236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        ArrayDeque<TreeNode> stack1 = new ArrayDeque<>();
        ArrayDeque<TreeNode> stack2 = new ArrayDeque<>();
        preOrderTraval(root, p, stack1);
        preOrderTraval(root, q, stack2);
        ArrayDeque<TreeNode> tmp = stack1.size() > stack2.size() ? stack1 : stack2;
        while (stack1.size() != stack2.size()) tmp.pollLast();
        while (stack1.peekLast() != stack2.peekLast()) {
            stack1.pollLast();
            stack2.pollLast();
        }
        return stack1.peekLast();
    }

    private boolean preOrderTraval(TreeNode node, TreeNode x, ArrayDeque<TreeNode> stack) {
        if (node == null) return false;
        if (node.val == x.val) {
            stack.offerFirst(node);
            return true;
        }
        if (preOrderTraval(node.left, x, stack)) {
            stack.offerFirst(node);
            return true;
        }
        if (preOrderTraval(node.right, x, stack)) {
            stack.offerFirst(node);
            return true;
        }
        return false;
    }


}
